The present invention pertains to the field of computers, computer software and similar technologies and, more particularly, to the deletion of expired items in a queue data structure.
In messaging systems the processing of messages is often regulated by means of a queuing system. A message queue is a data structure to which messages for processing by a message processor are added. Queues are characterized by their first-in-first-out nature which defines that items added to a queue first are removed from a queue first. Messages are typically added to a queue at the “tail” of the queue, whilst messages are typically removed from the queue at the “head” of the queue. Individual messages can have a useful life defined in terms of a time period for which they are valid. This can be implemented as a defined “time to live” or a particular expiry time. When working with a queue of messages it is useful to regularly review the messages in the queue to discard any messages which have expired (i.e. messages which have outlived their time to live). This is known as message expiry processing and provides for the message processor to not unnecessarily encounter expired messages in the queue.
Message expiry processing is typically undertaken at regular intervals. Alternatively, message expiry processing is undertaken every time one or a set of messages on the queue is processed. Message expiry processing is achieved by checking each and every item in a queue and determining if, for an item, the item has expired. Expired items are deleted from the queue whilst unexpired items are allowed to remain in the queue. The need to check every single item in the queue is time consuming, especially where the queue includes many items. Such message expiry processing is therefore undesirably resource intensive. Also, in some systems it is common for messages added to a queue to have a broadly increasing expiry time and so the likelihood of an unexpired message appearing near the tail of a queue is reduced. Additionally, it is common for a vast majority of messages in the queue to be unexpired, with a small minority that are expired and require deleting. In such circumstances it is undesirable to invest significantly in the deletion of expired items. Nonetheless, to be absolutely certain that no unexpired items remain in the queue it is necessary to check each and every item in the queue which is resource intensive.